<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-27 15:33:14
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-27 16:17:12
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最大二叉树</title>
</head>

<body>
    <script>
        // 给定一个不含重复元素的整数数组，一个依次数组构建的最大二叉树定义如下：
        // 二叉树的树根是数组的最大元素，
        // 左子树是通过数组中最大值左边部分构造的最大二叉树。
        // 右子树是通过数组中最大值右边部分构造最大二叉树。
        // 通过给定数组构建的最大二叉树，并且输出这个树的根节点

        // 思路
        // 构造树一般采用的是前序遍历，因为先构造中间部分，然后递归构造左子树，右子树。
        // 递归：
        // 1、确定递归函数的参数返回值，头结点
        // 2、终止条件，节点是大于0，如果节点是小于1的就是到了叶子节点。
        // 到了叶子节点后应该定义一个新节点，并把数组的值赋值给新节点。然后返回这个节点。表示一个数组大小是1的时候构造了一个新节点。
        // 确定单层递归
        // 1）找到数组中的最大值和对应下标，最大值确定根节点，下标切割数组
        // 2）最大值所在的左边构造左子树
        // 3）最大值的右边构造右子树
        class TreeNode {
            constructor(val, left, right) {
                this.val = (val === undefined ? 0 : val);
                this.left = (left === undefined ? null : left);
                this.right = (right === undefined ? null : right);
            }
        }

        var constructorMaxBinaryTree = function (num) {
            var buildTree = function (arr, left, right) {
                if (left > right) {
                    return null;
                }
                let maxVal = -1;
                let maxIndex = -1;
                for (let i = left; i <= right; ++i) {
                    if (arr[i] > maxVal) {
                        maxVal = arr[i];
                        maxIndex = i;
                    }

                }
                let root = new TreeNode(maxVal);
                root.left = buildTree(arr, left, maxIndex);
                root.right = buildTree(arr, maxIndex + 1, right);
                return root;
            }
            let root = buildTree(num, 0, num.length - 1,);
            return root;
        }



    </script>
</body>

</html>